package problems.contest;

import java.util.*;

/**
 * 第 90 场双周赛
 * <p>https://leetcode.cn/contest/biweekly-contest-90/</p>
 *
 * @author habitplus
 * @since 22:33, 2022/10/29
 */
public class BCT90 {
    /**
     * T1|6225. 差值数组不同的字符串
     * <p>https://leetcode.cn/problems/odd-string-difference/</p>
     */
    public String oddString(String[] words) {
        HashMap<String, Integer> map = new HashMap<>();
        int m = words.length;
        int[] ss = new int[2];
        int r = 0, n;
        String key;
        for (int j = 0; j < m; ++j) {
            StringBuilder sb = new StringBuilder();
            char[] chs = words[j].toCharArray();
            n = chs.length;
            // 转化成唯一的 key
            for (int i = 1; i < n; ++i) {
                sb.append(chs[i] - chs[i - 1]).append(',');
            }
            key = sb.toString();
            int k = map.getOrDefault(key, -1);

            if (j > 1) {
                if (map.size() > 1) {
                    if (k >= 0) {
                        return k == 0 ? words[ss[1]] : words[ss[0]];
                    } else {
                        return words[j];
                    }
                } else {
                    if (k == -1) {
                        ss[r] = j;
                        map.put(key, r);
                        ++r;
                    }
                }

            } else {
                if (k == -1) {
                    ss[r] = j;
                    map.put(key, r);
                    ++r;
                }
            }
        }

        return words[m - 1];

    }
    public String oddString1(String[] words) {
        int n = words.length;
        int res = 0;
        HashMap<String, int[]> ans = new HashMap<>();
        ArrayList<String> strings = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] ch = words[i].toCharArray();
            int len = ch.length;
            StringBuilder sb = new StringBuilder();
            for (int j = 1; j < len; j++) {
                sb.append(ch[j] - ch[j - 1]).append(',');
            }
            int[] cnt = ans.getOrDefault(sb.toString(), null);
            if (cnt == null) ans.put(sb.toString(), new int[] {i, 1});
            else ++cnt[1];

        }


        for(HashMap.Entry<String, int[]> e : ans.entrySet()) {
            int[] c = e.getValue();
            if (c[1] == 1) {
                res = c[0];
                break;
            }
        }

        return words[res];
    }



    /**
     * T2|6228. 距离字典两次编辑以内的单词
     * <p>https://leetcode.cn/problems/words-within-two-edits-of-dictionary/</p>
     */
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        List<String> ret = new ArrayList<>();

        for (String q : queries) {
            if (handle(q, dictionary)) ret.add(q);
        }

        return ret;
    }

    private boolean handle(String s, String[] dic) {
        int m = s.length();
        int steps;
        int j;
        for (String d : dic) {
            steps = 0;
            for (j = 0; j < m; ++j) {
                if (s.charAt(j) != d.charAt(j)) {
                    if (steps >= 2) break;
                    ++steps;
                }
            }

            if (steps < 3 && j == m) return true;
        }

        return false;
    }



    /**
     * T3|6226. 摧毁一系列目标
     * <p>https://leetcode.cn/problems/destroy-sequential-targets/</p>
     */
    public int destroyTargets(int[] nums, int space) {
        // 余数 -> [最小的数，个数]
        HashMap<Integer, int[]> cnt = new HashMap<>();

        int key;

        for (int num : nums) {
            key = num % space;
            int[] arr = cnt.getOrDefault(key, null);
            if (arr == null) {
                cnt.put(key, new int[] {num, 1});
            } else {
                arr[0] = Math.min(arr[0], num);
                ++arr[1];
            }
        }

        int ret = Integer.MAX_VALUE;
        int maxCnt = 0;
        for (HashMap.Entry<Integer, int[]> e : cnt.entrySet()) {
            int[] arr = e.getValue();
            if (arr[1] > maxCnt) {
                ret = arr[0];
                maxCnt = arr[1];
            } else if (arr[1] == maxCnt) {
                ret = Math.min(ret, arr[0]);
            }
        }

        return ret;
    }
}
